package com.xucy.springboot.common.MustPrettyTree;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * @Author xucy
 * @Date 2019-04-17 15:49
 * @Description 测试最优二叉树
 **/

public class TestMustPrettyTree {

    public static void main(String[] args) {
        int[] arr={3,7,8,29,5,11,23,14};
        createMustPrettyTree(arr);
    }

    public static Node createMustPrettyTree(int[] arr){

        //1.先使用数组中的所有元素创建若干个二叉树（只有一个节点）
        List<Node> treeList=new ArrayList();
        for(int val:arr){
            treeList.add(new Node(val));
        }

        //当集合中的树不是一颗的时候 说明还没有形成最优二叉树，继续循环
        while(treeList.size()>1){
            //2.排序
            Collections.sort(treeList);
            System.out.println(treeList);
            //3.取出来权值最小的两个二叉树
            Node left=treeList.get(treeList.size()-1);
            Node right=treeList.get(treeList.size()-2);
            //4.创建一个新的二叉树
            Node newTree=new Node(left.value+right.value);
            //5.把取出来的两个二叉树移除
            treeList.remove(treeList.size()-1);
            treeList.remove(treeList.size()-1);
            //6.放入原来的二叉树集合中
            treeList.add(newTree);
        }

        System.out.println(treeList);
        return treeList.get(0);
    }
}
